﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace ProblemsSet
{
    public class Problem_161 : BaseProblem
    {
        private List<bool[]> main;
        private int mnCount;
        private Dictionary<int, HashSet<int>> set;
        //private const int n = 12;
        //private const int m = 9;
        private const int n = 6;
        private const int m = 7;
        private int count;
        private Dictionary<int, HashSet<int>> empty;
        private Dictionary<int, HashSet<int>> fill;
        private Dictionary<int, int[]> inter;

        public override object GetResult()
        {
            count = m*n;
            mnCount = m*n/3;

            main = new List<bool[]>();
            set = new Dictionary<int, HashSet<int>>();
            empty = new Dictionary<int, HashSet<int>>();
            fill = new Dictionary<int, HashSet<int>>();
            inter = new Dictionary<int, int[]>();
            for (var y = 1; y <= n; y++)
            {
                for (var x = 1; x <= m; x++)
                {
                    var st = (y - 1)*m + x - 1;
                    empty.Add(st, new HashSet<int>());
                    fill.Add(st, new HashSet<int>());


                    int i1;
                    int i2;
                    int i3;

                    if (x < m - 1)
                    {
                        i1= (y - 1) * m + x - 1;
                        i2= (y - 1) * m + x;
                        i3= (y - 1) * m + x + 1;
                        InitIndecies(i1, i2, i3, st);
                    }

                    if (y < n - 1)
                    {
                        i1= (y - 1) * m + x - 1;
                        i2= (y) * m + x - 1;
                        i3= (y + 1) * m + x - 1;
                        InitIndecies(i1, i2, i3, st);
                    }

                    if (x >= m || y >= n) continue;

                    i1= (y - 1) * m + x - 1;
                    i2= (y - 1) * m + x;
                    i3= (y) * m + x;
                    InitIndecies(i1, i2, i3, st);

                    i1= (y - 1) * m + x - 1;
                    i2= (y - 1) * m + x;
                    i3 = (y)*m + x - 1;
                    InitIndecies(i1, i2, i3, st);

                    i1= (y - 1) * m + x - 1;
                    i2= (y) * m + x - 1;
                    i3= (y) * m + x;
                    InitIndecies(i1, i2, i3, st);

                    if (x == 1 && y == 1) continue;

                    i1= (y - 1) * m + x;
                    i2= (y) * m + x - 1;
                    i3= (y) * m + x;
                    InitIndecies(i1, i2, i3, st, true);
                }
            }

            for (var i = 0; i < main.Count; i++)
            {
                var tmp = new HashSet<int>();
                for (var j = i+1; j < main.Count; j++)
                {
                    var ex = true;
                    for (var k = 0; k < main[i].Length; k++)
                    {
                        if (!main[i][k] || !main[j][k]) continue;
                        ex = false;
                        break;
                    }
                    if (ex)
                        tmp.Add(j);
                }
                set.Add(i, tmp);
            }

            ulong res = 0;


            var start = new HashSet<int>();
            for (var i = 0; i < main.Count; i++)
            {
                start.Add(i);
            }

            Rec2(ref res, start, 0, new bool[count], 0);

            return res;
        }

        private void InitIndecies(int i1 ,int i2 , int i3, int cur)
        {
            InitIndecies(i1, i2, i3,cur, false);
        }

        private void InitIndecies(int i1 ,int i2 , int i3, int cur, bool isEmpty)
        {
            var tmp = new bool[count];
            tmp[i1] = true;
            tmp[i2] = true;
            tmp[i3] = true;
            main.Add(tmp);
            if (!isEmpty)
                fill[cur].Add(main.Count - 1);
            else
                empty[cur].Add(main.Count - 1);
            inter.Add(main.Count - 1, new []{i1, i2, i3});
        }

        private void Rec2(ref ulong result,  IEnumerable<int> curSet, int index, bool[] current, int cnt)
        {

            if (curSet.Count() < mnCount-cnt)
                return;


            if (current[index])
            {
                if (current[index+1])
                {
                    Rec2(ref result, curSet, index + 1, current, cnt);
                }
                else
                {
                    foreach (var i in empty[index].Where(curSet.Contains))
                    {
                        if (cnt == mnCount-1)
                        {
                            result++;
                            continue;
                        }
                        //newSet = new HashSet<int>(curSet);
                        //newSet.IntersectWith(set[i]);
                        //Rec2(ref result, newSet, index + 1, MergeBools(current, i), cnt+1);
                        //var ns = curSet.Intersect(set[i]).ToList();
                        Rec2(ref result, curSet.Intersect(set[i]).ToList(), index + 1, MergeBools(current, i), cnt + 1);
                    }
                    Rec2(ref result, curSet, index + 1, current, cnt);
                }
            }
            else
            {
                foreach (var i in fill[index].Where(curSet.Contains))
                {
                    if (cnt == mnCount - 1)
                    {
                        result++;
                        continue;
                    }
                    //var ns = curSet.Intersect(set[i]).ToList();
                    Rec2(ref result, curSet.Intersect(set[i]).ToList(), index + 1, MergeBools(current, i), cnt + 1);
                    //newSet = new HashSet<int>(curSet);
                    //newSet.IntersectWith(set[i]);
                    //Rec2(ref result, newSet, index + 1, MergeBools(current, i), cnt+1);
                }
            }

        }

        private bool[] MergeBools(bool[] first, int second)
        {
            var res = new bool[count];
            first.CopyTo(res, 0);
            
            foreach (var b in inter[second])
            {
                res[b] = true;
            }

            return res;
        }

        public override string Problem
        {
            get
            {
                return @"A triomino is a shape consisting of three squares joined via the edges. There are two basic forms:



If all possible orientations are taken into account there are six:



Any n by m grid for which nxm is divisible by 3 can be tiled with triominoes.
If we consider tilings that can be obtained by reflection or rotation from another tiling as different there are 41 ways a 2 by 9 grid can be tiled with triominoes:



In how many ways can a 9 by 12 grid be tiled in this way by triominoes?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return false;
            }
        }

        public override object Answer
        {
            get
            {
                return null;
            }
        }

    }
}
